package DP;

import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Set;

/**
 * @Classname JZ49丑数
 * @Description TODO
 * @Date 2022/12/27 22:08
 * @Created by xjl
 */
public class JZ49丑数 {

    public int nthUglyNumber(int n) {
        int[] factors = {2, 3, 5};
        Set<Long> set = new HashSet<>();
        PriorityQueue<Long> queue = new PriorityQueue<>();
        set.add(1L);
        queue.add(1L);
        int ugly = 0;
        for (int i = 0; i < n; i++) {
            // 最小的值
            Long curr = queue.poll();
            ugly = Math.toIntExact(curr);
            for (int fa : factors) {
                long next = curr * fa;
                if (set.add(next)) {
                    queue.add(next);
                }
            }
        }
        return ugly;
    }

    public int nthUglyNumber2(int n) {
        int[] dp = new int[n + 1];
        dp[1] = 1;
        int p2 = 1, p3 = 1, p5 = 1;
        for (int i = 2; i <= n; i++) {
            int num2 = dp[p2] * 2, num3 = dp[p3] * 3, num5 = dp[p5] * 5;
            dp[i] = Math.min(Math.min(num2, num3), num5);
            if (dp[i] == num2) {
                p2++;
            }
            if (dp[i] == num3) {
                p3++;
            }
            if (dp[i] == num5) {
                p5++;
            }
        }
        return dp[n];
    }
}
